#include <deque>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int kMaxN = 3030;
const int kInf = 1e9;

struct Graph {
  int n;
  vector<pair<int, int>> g[kMaxN];
  int dist[kMaxN];
  int cnt[kMaxN];
  bool in_que[kMaxN];
  int h[kMaxN];
  deque<int> que;

  void AddEdge(int u, int v, int w) {
    g[u].emplace_back(v, w);
  }

  void Renew(int v, int d, int path_len) {
    if (dist[v] > d) {
      dist[v] = d;
      if (!in_que[v]) {
        in_que[v] = true;
        que.push_back(v);
      }
      cnt[v] = path_len;
    }
  }

  bool SPFA() {
    fill(dist, dist + n + 1, kInf);
    fill(cnt, cnt + n + 1, 0);
    fill(in_que, in_que + n + 1, false);
    for (int i = 1; i <= n; i++) {
      Renew(i, 0, 0);
    }
    while (!que.empty()) {
      int u = que.front();

      in_que[u] = false;
      que.pop_front();
      for (const pair<int, int>& e : g[u]) {
        Renew(e.first, dist[u] + e.second, cnt[u] + 1);
        if (cnt[e.first] >= n) {
          return false;
        }
      }
    }
    return true;
  }

  void Dijkstra(int s) {
    priority_queue<pair<int, int>> pq;
    fill(dist, dist + n + 1, kInf);
    dist[s] = 0;
    pq.emplace(-dist[s], s);
    while (!pq.empty()) {
      int d = -pq.top().first, u = pq.top().second;

      pq.pop();
      if (dist[u] != d) {
        continue;
      }
      for (const pair<int, int>& e : g[u]) {
        int v = e.first;

        if (dist[v] > d + e.second + h[u] - h[v]) {
          dist[v] = d + e.second + h[u] - h[v];
          pq.emplace(-dist[v], v);
        }
      }
    }
  }

  void Johnson() {
    if (!SPFA()) {
      cout << "-1\n";
      return;
    }
    for (int i = 1; i <= n; i++) {
      h[i] = dist[i];
    }
    for (int i = 1; i <= n; i++) {
      long long ans = 0;
      Dijkstra(i);
      for (int j = 1; j <= n; j++) {
        if (dist[j] == kInf) {
          ans += (long long)j * dist[j];
        } else {
          ans += (long long)j * (dist[j] - h[i] + h[j]);
        }
      }
      cout << ans << "\n";
    }
  }
};

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  Graph graph;
  int m;
  cin >> graph.n >> m;
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    graph.AddEdge(u, v, w);
  }
  graph.Johnson();
  return 0;
}